package nowCoder;

/**
 * Created by Ghost on 2015/3/24.
 * Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
 You should preserve the original relative order of the nodes in each of the two partitions.
 For example,
 Given1->4->3->2->5->2and x = 3,
 return1->2->2->4->3->5.
 */
public class Partition_list {
    public ListNode partition(ListNode head, int x) {
        if(head==null || head.next==null)
            return head;

        ListNode pre = null, cur = head, h=head, tail, origintail;
        ListNode tmp = head;
        while(tmp.next!=null){
            tmp = tmp.next;
        }

        tail = tmp;
        origintail = tmp;
        while(cur!=null && cur!=origintail){//
            if(cur.val<x){
                pre = cur;
                cur = cur.next;
            } else{
                if(pre==null){

                    h = cur.next;
                    cur.next = null;
                    tail.next = cur;
                    cur = h;
                } else{
                    pre.next = cur.next;
                    cur.next = null;
                    tail.next = cur;
                    cur = pre.next;
                }
                tail = tail.next;
            }
        }

        if(cur==origintail){
            if(cur.val>=x){
                if(pre==null){

                    h = cur.next;
                    cur.next = null;
                    tail.next = cur;
                } else{
                    if(cur.next!=null){
                        pre.next = cur.next;
                        cur.next = null;
                        tail.next = cur;
                    }
                }
            }
        }
        return h;
    }

    public static void main(String[] args){
        Partition_list partition_list = new Partition_list();
        ListNode root = new ListNode(1);
        root.next = new ListNode(4);
        root.next.next = new ListNode(3);
        root.next.next.next = new ListNode(2);
        root.next.next.next.next = new ListNode(5);
        root.next.next.next.next.next = new ListNode(2);
        ListNode h = partition_list.partition(root,4);
        while(h!=null){
            System.out.println(h.val);
            h = h.next;
        }
    }
}
